#coding=utf-8
from sparse import sparse

x,y = 0,0

class Node(object):
    def __init__(self, data, parent=None):
        self.data = data
        self.parent = parent
        self.children = []
        
    def __repr__(self):
        return self.word
    __str__ = __repr__
        
    def add_child(self, child):
        self.children.append(child)
    
    def toSparse(self, sparse):
        global x,y
        
        sparse[(x,y)] = self.data
        if not self.children:return
        
        x0 = x
        x = x + 1
        y = y - 1
        
        for child in self.children:
            y = y + 1
            child.toSparse(sparse)
            
        x = x0
    
    def toList(self, list_):
        list_.append(self.data)
        if not self.children:return
        for child in self.children:
            child.toList(list_)
            
class Tree(object):
    def __init__(self, node):
        self.root = node
        
    def toSparse(self):
        
        sp = sparse()
        
        global x,y
        x,y = 0,0
        self.root.toSparse(sp)
        
        return sp
    
    def toList(self):
        l = []
        self.root.toList(l)
        
        return l

